package 分治.middle;

/**
 * @author Lw中
 * @date 2021/7/29 23:03
 */
public class WuShi {

    // 50. Pow(x, n)

    // 方法1：快速幂 + 递归（分治）
    public double myPow(double x, int n) {
//        if (n == 0) {
//            return 1;
//        }
//        if (n == 1) {
//            return x;
//        }
//        if (n < 0) {
//            return 1 / myPow(x, -n);
//        }
//        if (n % 2 == 0) {
//            return myPow(x * x, n / 2);
//        }
//        return x * myPow(x, n - 1);
        /**
         * LWZ TODO : 2021/7/29 对于递归写法模糊不清
         *
         */
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    private double quickMul(double x, long l) {
        if (l == 0) {
            return 1.0;
        }
        double y = quickMul(x, l / 2);
        return l % 2 == 0 ? y * y : y * y * x;
    }

}
